home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / DJGPP / LGP250S1.ZIP / src / libgplus.5 / libgplus / tests / tbag.cc < prev    next >
C/C++ Source or Header  |  1993-06-06  |  14KB  |  533 lines
  1. /*
  2.  a test file for Bags
  3. */
  4.  
  5.  
  6. #ifdef PTIMES
  7. const int ptimes = 1;
  8. #else
  9. const int ptimes = 0;
  10. #endif
  11.  
  12. #include <stream.h>
  13. #include <assert.h>
  14. #include <builtin.h>
  15.  
  16. #define tassert(ex) { cerr << #ex; \
  17.                        if ((ex)) cerr << " OK\n"; \
  18.                        else cerr << " Fail\n"; }
  19.  
  20. #include "iBag.h"
  21.  
  22. unsigned int hash(int x) { return multiplicativehash(x) ; }
  23.  
  24. int SIZE;
  25.  
  26. int *nums;
  27. int *odds;
  28. int *dups;
  29.  
  30. void add(int x[], intBag& a)
  31. {
  32.   for (int i = 0; i < SIZE; ++i) a.add(x[i]);
  33. }
  34.  
  35.  
  36. #include <MLCG.h>
  37.  
  38. MLCG randgen;
  39.  
  40. void permute(int x[])
  41. {
  42.   for (int i = 1; i < SIZE; ++i)
  43.   {
  44.     int j = randgen.asLong() % (i + 1);
  45.     int tmp = x[i]; x[i] = x[j]; x[j] = tmp;
  46.   }
  47. }
  48.  
  49. void makenums()
  50. {
  51.   for (int i = 0; i < SIZE; ++i) nums[i] = i + 1;
  52. }
  53.  
  54. void makeodds()
  55. {
  56.   for (int i = 0; i < SIZE; ++i) odds[i] = 2 * i + 1;
  57.   permute(odds);
  58. }
  59.  
  60. void makedups()
  61. {
  62.   for (int i = 0; i < SIZE; i += 2) dups[i] = dups[i+1] = i/2 + 1;
  63.   permute(dups);
  64. }
  65.  
  66. void printBag(intBag& a)
  67. {
  68.   int maxprint = 20;
  69.   cout << "[";
  70.   int k = 0;
  71.   for (Pix i = a.first(); i != 0 && k < maxprint; a.next(i),++k) 
  72.     cout << a(i) << " ";
  73.   if (i != 0) cout << "...]\n";
  74.   else cout << "]\n";
  75. }
  76.  
  77.  
  78. void generictest(intBag& a, intBag& b, intBag& c)
  79. {
  80.   c.clear();
  81.   assert(c.empty());
  82.   for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
  83.   for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
  84.   c.del(a(a.first()));
  85.   Pix i = a.first();
  86.   assert(!c.contains(a(i)));
  87.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  88.   c.add(a(a.first()));
  89.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  90.   for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
  91.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  92.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  93.   for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
  94.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  95.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  96.   assert(c.empty());
  97.   assert(a.OK());
  98.   assert(b.OK());
  99.   assert(c.OK());
  100. }
  101.  
  102. #include "iXPBag.h"
  103.  
  104. void XPtest()
  105. {
  106.   intXPBag a(SIZE);
  107.   add(nums, a);
  108.   assert(a.length() == SIZE);
  109.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  110.   intXPBag b(SIZE);
  111.   add(odds, b);
  112.   assert(b.length() == SIZE);
  113.   intXPBag c(SIZE);
  114.   add(dups, c); 
  115.   assert(c.length() == SIZE);
  116.   intXPBag d(a);
  117.   add(nums, d);
  118.   assert(d.length() == SIZE*2);
  119.   cout << "a: "; printBag(a);
  120.   cout << "b: "; printBag(b);
  121.   cout << "c: "; printBag(c);
  122.   cout << "d: "; printBag(d);
  123.   for (j = 1; j <= SIZE; ++j) assert(d.nof(j) == 2);
  124.   d.del(1);
  125.   assert(d.nof(1) == 1);
  126.   d.del(1);
  127.   assert(d.nof(1) == 0);
  128.   d.remove(2);
  129.   assert(!d.contains(2));
  130.   for (Pix l = c.first(); l; c.next(l)) d.remove(c(l));
  131.   assert(d.length() == SIZE);
  132.   
  133.   c.clear();
  134.   assert(c.empty());
  135.   for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
  136.   for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
  137.   c.del(a(a.first()));
  138.   Pix i = a.first();
  139.   assert(!c.contains(a(i)));
  140.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  141.   c.add(a(a.first()));
  142.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  143.   for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
  144.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  145.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  146.   for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
  147.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  148.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  149.   assert(c.empty());
  150.   assert(a.OK());
  151.   assert(b.OK());
  152.   assert(c.OK());
  153.  
  154.   generictest(a, b, c);
  155. }
  156.  
  157.  
  158. #include "iSLBag.h"
  159.  
  160. void SLtest()
  161. {
  162.   intSLBag a;
  163.   add(nums, a);
  164.   assert(a.length() == SIZE);
  165.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  166.   intSLBag b;
  167.   add(odds, b);
  168.   assert(b.length() == SIZE);
  169.   intSLBag c;
  170.   add(dups, c); 
  171.   assert(c.length() == SIZE);
  172.   intSLBag d(a);
  173.   add(nums, d);
  174.   assert(d.length() == SIZE*2);
  175.   cout << "a: "; printBag(a);
  176.   cout << "b: "; printBag(b);
  177.   cout << "c: "; printBag(c);
  178.   cout << "d: "; printBag(d);
  179.   for (j = 1; j <= SIZE; ++j) assert(d.nof(j) == 2);
  180.   d.del(1);
  181.   assert(d.nof(1) == 1);
  182.   d.del(1);
  183.   assert(d.nof(1) == 0);
  184.   d.remove(2);
  185.   assert(!d.contains(2));
  186.   for (Pix l = c.first(); l; c.next(l)) d.remove(c(l));
  187.   assert(d.length() == SIZE);
  188.   
  189.   c.clear();
  190.   assert(c.empty());
  191.   for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
  192.   for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
  193.   c.del(a(a.first()));
  194.   Pix i = a.first();
  195.   assert(!c.contains(a(i)));
  196.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  197.   c.add(a(a.first()));
  198.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  199.   for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
  200.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  201.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  202.   for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
  203.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  204.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  205.   assert(c.empty());
  206.   assert(a.OK());
  207.   assert(b.OK());
  208.   assert(c.OK());
  209.  
  210.   generictest(a, b, c);
  211. }
  212.  
  213.  
  214. #include "iVHBag.h"
  215.  
  216. void VHtest()
  217. {
  218.   intVHBag a(SIZE);
  219.   add(nums, a);
  220.   assert(a.length() == SIZE);
  221.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  222.   intVHBag b(SIZE);
  223.   add(odds, b);
  224.   assert(b.length() == SIZE);
  225.   intVHBag c(SIZE);
  226.   add(dups, c); 
  227.   assert(c.length() == SIZE);
  228.   intVHBag d(a);
  229.   add(nums, d);
  230.   assert(d.length() == SIZE*2);
  231.   cout << "a: "; printBag(a);
  232.   cout << "b: "; printBag(b);
  233.   cout << "c: "; printBag(c);
  234.   cout << "d: "; printBag(d);
  235.   for (j = 1; j <= SIZE; ++j) assert(d.nof(j) == 2);
  236.   d.del(1);
  237.   assert(d.nof(1) == 1);
  238.   d.del(1);
  239.   assert(d.nof(1) == 0);
  240.   d.remove(2);
  241.   assert(!d.contains(2));
  242.   for (Pix l = c.first(); l; c.next(l)) d.remove(c(l));
  243.   assert(d.length() == SIZE);
  244.   
  245.   c.clear();
  246.   assert(c.empty());
  247.   for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
  248.   for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
  249.   c.del(a(a.first()));
  250.   Pix i = a.first();
  251.   assert(!c.contains(a(i)));
  252.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  253.   c.add(a(a.first()));
  254.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  255.   for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
  256.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  257.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  258.   for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
  259.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  260.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  261.   assert(c.empty());
  262.   assert(a.OK());
  263.   assert(b.OK());
  264.   assert(c.OK());
  265.  
  266.   generictest(a, b, c);
  267. }
  268.  
  269. #include "iCHBag.h"
  270.  
  271. void CHtest()
  272. {
  273.   intCHBag a(SIZE);
  274.   add(nums, a);
  275.   assert(a.length() == SIZE);
  276.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  277.   intCHBag b(SIZE);
  278.   add(odds, b);
  279.   assert(b.length() == SIZE);
  280.   intCHBag c(SIZE);
  281.   add(dups, c); 
  282.   assert(c.length() == SIZE);
  283.   intCHBag d(a);
  284.   add(nums, d);
  285.   assert(d.length() == SIZE*2);
  286.   cout << "a: "; printBag(a);
  287.   cout << "b: "; printBag(b);
  288.   cout << "c: "; printBag(c);
  289.   cout << "d: "; printBag(d);
  290.   for (j = 1; j <= SIZE; ++j) assert(d.nof(j) == 2);
  291.   d.del(1);
  292.   assert(d.nof(1) == 1);
  293.   d.del(1);
  294.   assert(d.nof(1) == 0);
  295.   d.remove(2);
  296.   assert(!d.contains(2));
  297.   for (Pix l = c.first(); l; c.next(l)) d.remove(c(l));
  298.   assert(d.length() == SIZE);
  299.   
  300.   c.clear();
  301.   assert(c.empty());
  302.   for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
  303.   for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
  304.   c.del(a(a.first()));
  305.   Pix i = a.first();
  306.   assert(!c.contains(a(i)));
  307.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  308.   c.add(a(a.first()));
  309.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  310.   for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
  311.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  312.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  313.   for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
  314.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  315.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  316.   assert(c.empty());
  317.   assert(a.OK());
  318.   assert(b.OK());
  319.   assert(c.OK());
  320.  
  321.   generictest(a, b, c);
  322. }
  323.  
  324. #include "iOXPBag.h"
  325.  
  326. void OXPtest()
  327. {
  328.   intOXPBag a(SIZE);
  329.   add(nums, a);
  330.   assert(a.length() == SIZE);
  331.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  332.   intOXPBag b(SIZE);
  333.   add(odds, b);
  334.   assert(b.length() == SIZE);
  335.   intOXPBag c(SIZE);
  336.   add(dups, c); 
  337.   assert(c.length() == SIZE);
  338.   intOXPBag d(a);
  339.   add(nums, d);
  340.   assert(d.length() == SIZE*2);
  341.   cout << "a: "; printBag(a);
  342.   cout << "b: "; printBag(b);
  343.   cout << "c: "; printBag(c);
  344.   cout << "d: "; printBag(d);
  345.   for (j = 1; j <= SIZE; ++j) assert(d.nof(j) == 2);
  346.   d.del(1);
  347.   assert(d.nof(1) == 1);
  348.   d.del(1);
  349.   assert(d.nof(1) == 0);
  350.   d.remove(2);
  351.   assert(!d.contains(2));
  352.   for (Pix l = c.first(); l; c.next(l)) d.remove(c(l));
  353.   assert(d.length() == SIZE);
  354.   
  355.   c.clear();
  356.   assert(c.empty());
  357.   for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
  358.   for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
  359.   c.del(a(a.first()));
  360.   Pix i = a.first();
  361.   assert(!c.contains(a(i)));
  362.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  363.   c.add(a(a.first()));
  364.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  365.   for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
  366.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  367.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  368.   for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
  369.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  370.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  371.   assert(c.empty());
  372.   assert(a.OK());
  373.   assert(b.OK());
  374.   assert(c.OK());
  375.  
  376.   generictest(a, b, c);
  377. }
  378.  
  379.  
  380. #include "iOSLBag.h"
  381.  
  382. void OSLtest()
  383. {
  384.   intOSLBag a;
  385.   add(nums, a);
  386.   assert(a.length() == SIZE);
  387.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  388.   intOSLBag b;
  389.   add(odds, b);
  390.   assert(b.length() == SIZE);
  391.   intOSLBag c;
  392.   add(dups, c); 
  393.   assert(c.length() == SIZE);
  394.   intOSLBag d(a);
  395.   add(nums, d);
  396.   assert(d.length() == SIZE*2);
  397.   cout << "a: "; printBag(a);
  398.   cout << "b: "; printBag(b);
  399.   cout << "c: "; printBag(c);
  400.   cout << "d: "; printBag(d);
  401.   for (j = 1; j <= SIZE; ++j) assert(d.nof(j) == 2);
  402.   d.del(1);
  403.   assert(d.nof(1) == 1);
  404.   d.del(1);
  405.   assert(d.nof(1) == 0);
  406.   d.remove(2);
  407.   assert(!d.contains(2));
  408.   for (Pix l = c.first(); l; c.next(l)) d.remove(c(l));
  409.   assert(d.length() == SIZE);
  410.   
  411.   c.clear();
  412.   assert(c.empty());
  413.   for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
  414.   for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
  415.   c.del(a(a.first()));
  416.   Pix i = a.first();
  417.   assert(!c.contains(a(i)));
  418.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  419.   c.add(a(a.first()));
  420.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  421.   for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
  422.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  423.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  424.   for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
  425.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  426.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  427.   assert(c.empty());
  428.   assert(a.OK());
  429.   assert(b.OK());
  430.   assert(c.OK());
  431.  
  432.   generictest(a, b, c);
  433. }
  434.  
  435. #include "iSplayBag.h"
  436.  
  437. void Splaytest()
  438. {
  439.   intSplayBag a;
  440.   add(nums, a);
  441.   assert(a.length() == SIZE);
  442.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  443.   intSplayBag b;
  444.   add(odds, b);
  445.   assert(b.length() == SIZE);
  446.   intSplayBag c;
  447.   add(dups, c); 
  448.   assert(c.length() == SIZE);
  449.   intSplayBag d(a);
  450.   add(nums, d);
  451.   assert(d.length() == SIZE*2);
  452.   cout << "a: "; printBag(a);
  453.   cout << "b: "; printBag(b);
  454.   cout << "c: "; printBag(c);
  455.   cout << "d: "; printBag(d);
  456.   for (j = 1; j <= SIZE; ++j) assert(d.nof(j) == 2);
  457.   d.del(1);
  458.   assert(d.nof(1) == 1);
  459.   d.del(1);
  460.   assert(d.nof(1) == 0);
  461.   d.remove(2);
  462.   assert(!d.contains(2));
  463.   for (Pix l = c.first(); l; c.next(l)) d.remove(c(l));
  464.   assert(d.length() == SIZE);
  465.   
  466.   c.clear();
  467.   assert(c.empty());
  468.   for (Pix k = a.first(); k != 0; a.next(k)) c.add(a(k));
  469.   for (k = a.first(); k != 0; a.next(k)) assert(c.contains(a(k)));
  470.   c.del(a(a.first()));
  471.   Pix i = a.first();
  472.   assert(!c.contains(a(i)));
  473.   for (a.next(i); i != 0; a.next(i)) assert(c.contains(a(i)));
  474.   c.add(a(a.first()));
  475.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  476.   for (k = b.first(); k != 0; b.next(k)) c.add(b(k));
  477.   for (i = b.first(); i != 0; b.next(i)) assert(c.contains(b(i)));
  478.   for (i = a.first(); i != 0; a.next(i)) assert(c.contains(a(i)));
  479.   for (k = a.first(); k != 0; a.next(k)) c.remove(a(k));
  480.   for (i = a.first(); i != 0; a.next(i)) assert(!c.contains(a(i)));
  481.   for (i = b.first(); i != 0; b.next(i)) c.del(b(i));
  482.   assert(c.empty());
  483.   assert(a.OK());
  484.   assert(b.OK());
  485.   assert(c.OK());
  486.  
  487.   generictest(a, b, c);
  488. }
  489.  
  490.  
  491. double return_elapsed_time ( double );
  492. double start_timer ( void );
  493.  
  494. int main(int argv, char** argc)
  495. {
  496.   if (argv > 1)
  497.   {
  498.     SIZE = abs(atoi(argc[1]));
  499.     SIZE &= ~1;
  500.   }
  501.   else
  502.     SIZE = 100;
  503.   nums = new int[SIZE];
  504.   odds = new int[SIZE];
  505.   dups = new int[SIZE];
  506.   makenums();
  507.   makeodds();
  508.   makedups();
  509.   start_timer();
  510.   cout << "VHtest\n"; VHtest();
  511.   if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  512.   start_timer();
  513.   cout << "CHtest\n"; CHtest();
  514.   if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  515.   start_timer();
  516.   cout << "SLtest\n"; SLtest();
  517.   if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  518.   start_timer();
  519.   cout << "XPtest\n"; XPtest();
  520.   if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  521.   start_timer();
  522.   cout << "Splaytest\n"; Splaytest();
  523.   if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  524.   start_timer();
  525.   cout << "OSLtest\n"; OSLtest();
  526.   if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  527.   start_timer();
  528.   cout << "OXPtest\n"; OXPtest();
  529.   if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  530.  
  531.   return 0;
  532. }
  533.